\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[left=2cm, right=2cm, top=1cm, bottom=1cm]{geometry}
\usepackage{graphicx}

\title{Projet Ada-dico, implémentation d'une table de hachage}
\date{}
\author{Arnaud Maillet}

\begin{document}

\maketitle

\bigskip

\section{Choix d'implémentation}

\bigskip

\par{Le table de hachage a été implémentée avec un tableau de type "Array" et des listes triées simples. L'implémentation par une liste triée a été choisie pour optimiser le parcours de la table de hachage, sur des milliers d'éléments cela peut faire la différence par rapport à une liste simple (pour certaines fonctions de hachage avec une mauvaise répartition dans le tableau)}.

\bigskip

\par{La table de hachage dispose d'une méthode Vider qui permet de vider la table.\\
Il y a une methode Redim qui permet de redimensionner la table lors de l'insertion ou la suppression. Quand on insère, on agrandit deux fois la table lorsque il y a une moyenne de 4 mots par case de tableau. Et quand on supprime on réduit par deux la taille de la table lorsque le nombre de mots est égal à la moitié de la taille du tableau.\\
Il y a une méthode Trouve qui permet de chercher un mot dans la table, cette procédure renvoit un booléen et la définition du mot cherché si celui ci a été trouvé.\\
On dispose d'une methode Inserer et Supprime, celles ci permettent d'insérer et de supprimer un mot dans une table de hachage.\\
On a une methode Remplit\_Dico qui permet d'insérer le contenu d'un fichier texte dans la table de hachage et une méthode Supprime\_Mots qui supprime tous les mots d'un fichier texte dans la table de hachage. Cette dernière est utilisée surtout pour certains tests.\\
La procédure dispersion est utilisée pour faire des statistiques sur la table de hachage.\\}

\section{Jeu de tests de la table de hachage}

\bigskip

\par{Un jeu de tests pour la table de hachage a été mis en place. On va tester la table de hachage sur un mini dictionnaire, un dictionnaire vide, un dictionnaire unitaire ou même un gros dictionnaire. Les différentes méthodes proposées par la table de hachage sont toutes testées dans différentes configurations. Les 5 fonctions de hachage sont aussi testés par le jeu de test. En effet les 5 fonctions de hachage sont assez différentes les unes des autres et elles permettent d'avoir les mots dans des dispositions différentes. Cela permet de remonter des bugs qui seraient peut être invisibles avec qu'une seule fonction de hachage. En effet lors du développement de la table de hachage un bug dans Inserer était présent (liste pas bien triée) et le bug était visible que sur certaines méthodes de hachage et non sur toutes.}
\bigskip
Pour lancer le jeu de tests il suffit juste de taper la commande : ./launch\_tests dans le repertoire du projet.

\bigskip
\newpage
Exemple de tests réussis :

\bigskip

\includegraphics[height=100mm]{launchtestspassed.jpg}

\bigskip

Exemple de test échoué :

\bigskip

\includegraphics[height=50mm]{launchtestsfailed.jpg}

\section{Démonstration de la table de hachage}

\bigskip

\par{Un script shell a été fait pour voir une démonstration de la table de hachage. Cette démonstration permet d'avoir une vue assez globale des fonctions proposées par la table de hachage. Elle remplit la table de hachage avec 21 élements. On affiche le contenu de la table, on fait des recherches, des suppressions de mots. On redimensionne, vide la table de hachage. Cette démonstration est assez complète et il suffit de taper la commande : ./launch\_demonstration pour voir la démonstration.}

\section{Statistiques de la table de hachage}

\bigskip

\par{Un script a été fait pour voir les statistiques des différentes fonctions de hachage. Il suffit de lancer le script en faisant : ./launch\_stats dans le répertoire du projet. Ces statistiques nous donnent le nombre de mot, la forme de la table, le nombre moyen de mots par cases et l'écart type.}\\

\bigskip

Les statistiques :\\

\bigskip

\includegraphics[height=117mm]{launchstats.jpg}

\bigskip

\par{Ces statistiques nous permettent de conclure que la fonction de hachage "Hash\_Somme" est la plus interessante pour une table de hachage car elle possède la meilleur répartition dans le tableau alors que Hash\_Bete est la moins interessante.}\\

\section{Benchmarks}

\bigskip

\par{Des benchmarks on été faits pour tester la performance des différentes fonctions de hachage. Le benchmark consiste à insérer 100 000 mots dans la table de hachage puis de supprimer ces 100 000 mots. Les benchmarks sur la table de hachage demandent un ordinateur assez puissant car ils consomment beaucoup de ressources.}\\

\bigskip

Lancement des benchmarks :\\

\bigskip

\includegraphics[height=110mm]{launchbenchmarks.jpg}

\bigskip

Ces benchmarks nous permettent de conclure que la fonction de hachage "Hash\_Somme" est la plus performante et que la fonction "Hash\_Bete" est la plus lente pour une table de hachage.

\section{Readme}

Ada-dico : implémentation d'une table de hachage en Ada\\

\bigskip

Dépendances requises : gnat bash\\

\bigskip

Installation des dépendances sous debian/ubuntu : aptitude install gnat bash\\

\bigskip

UTILISATION :\\

\bigskip

Pour lancer les jeux de tests : ./launch\_tests\\

\bigskip

Pour lancer la démonstration de la table de hachage : ./launch\_demonstration\\

\bigskip

Pour lancer les statistiques de la table avec les différentes fonctions de hachage qui existent : ./launch\_stats\\

\bigskip

Pour lancer les benchmarks de la table avec les différentes fonctions de hachage qui existent : ./launch\_benchmarks

\newpage

\section{Divers}

\bigskip

\par{Mercurial (Gestionnaire de version) a été utilisé pour avoir une trace précise de tout ce qui a été fait tout au long du projet. Cela permet de savoir quelles modifications ont été faites d'un commit à l'autre, de comprendre et de pouvoir revenir en arrière lorsque un bug est présent. Cela a permis aussi de centraliser le projet et d'y avoir accès depuis n'importe où}.

\bigskip
\bigskip

\includegraphics[height=195mm]{mercurial.jpg}

\end{document}
